Data compression is the process of converting data to be stored using less bits. The two types of data compression are lossy and lossless. Lossy data compression compresses data to a greater degree, but loses data during the process. Thus, during decompression, the data is an approximation of its original form rather than an exact replica. Lossless data compression compresses data to a lesser degree, but does not lose any data during the process. Accordingly, during decompression, the data is reconstructed exactly as it was before compression. The objective of data compression is to reduce the amount of bandwidth necessary for transmission and/or memory necessary for storage.
An example of a common lossless compression technique is Huffman coding. Huffman coding is based on the frequency of occurrence of a data item. The technique uses a lower number of bits to encode the data that occurs more frequently. Unfortunately, a limitation of Huffman coding is that it has a fixed sequence length procedure and cannot compress redundancy in data that exceeds the sequence length. As a result, Huffman coding is complex and requires a large amount of memory to be effective. Huffman coding involves performing an analysis of the entire file before any part of the file can be extracted. Further, the Huffman technique is asymmetrical by nature, meaning the decoding process is much slower than the encoding process. Such a characteristic is unacceptable for certain hardware implementations because a computer is generally designed to read and write approximately the same amount of data on a single clock cycle.
Another common lossless technique is the Lempel-Ziv-Welch method (LZW). LZW automatically builds a dictionary of previously seen strings in the data file being compressed. The dictionary starts off with 256 entries, one for each possible character. Every time a string not already in the dictionary is seen, a longer string consisting of that string is appended. The output consists of integer indices into the dictionary. Unfortunately, LZW suffers by virtue of the string table it generates. The dictionary can get very large in a short amount of time. In addition, the amount of storage needed is indeterminate, as the amount of memory needed depends on the total length of all the strings. Also, as with Huffman encoding, the entire file must be encoded and/or decoded before any part of the file is compressed and/or decompressed. Further, the entire process is asymmetrical in nature and takes a considerable amount of time longer compressing than decompressing.
Apart from the limitations imposed by the above compression techniques, another major problem is the lack of a uniform compression method for different formats of data. For example, a computer graphic composed of pixels can be represented using Z-buffering. Z-buffering works by testing pixel depth and comparing the current position of the Z coordinate, with data stored in the Z-buffer. The Z-buffer stores information about the last position of each pixel. The pixel in the closer position to the viewer is the one that will be displayed. Other common data formats used to represent graphics composed of pixels are color buffering and normal maps. Currently, there is no lossless compression technique for normal map data, and color buffering data requires a distinct compression method that is software-oriented.
What is needed is a data compression/decompression method that is symmetrical in nature and thereby suitable for hardware implementation. Further, what is needed is a data compression/decompression method that can compress and decompress several different data formats, including normal map data. In addition, what is needed is a data compression/decompression method that is adaptable to a variety of graphical hardware devices.